class Solution:
    def numIslands(self, grid) -> int:
        rows = len(grid)
        if rows == 0:
            return 0
        cols = len(grid[0])

        def dfs(grid, pb, row, col, rows, cols):
            # 候选节点就是当前节点的上下左右节点
            if row - 1 >= 0:
                if not pb[row - 1][col] and grid[row - 1][col] == '1':
                    pb[row - 1][col] = True
                    dfs(grid, pb, row - 1, col, rows, cols)
            if row + 1 < rows:
                if not pb[row + 1][col] and grid[row + 1][col] == '1':
                    pb[row + 1][col] = True
                    dfs(grid, pb, row + 1, col, rows, cols)

            if col - 1 >= 0:
                if not pb[row][col - 1] and grid[row][col - 1] == '1':
                    pb[row][col - 1] = True
                    dfs(grid, pb, row, col - 1, rows, cols)

            if col + 1 < cols:
                if not pb[row][col + 1] and grid[row][col + 1] == '1':
                    pb[row][col + 1] = True
                    dfs(grid, pb, row, col + 1, rows, cols)
        res = 0
        pb = [[False] * cols for _ in range(rows)]
        for i in range(rows):
            for j in range(cols):
                if not pb[i][j] and grid[i][j] == '1':
                    pb[i][j] = True
                    dfs(grid, pb, i, j, rows, cols)#一次遍历就会找到一个连通。
                    res += 1
        return res


if __name__ == '__main__':
    #leetcode 113
    grid = [
        ['1', '1', '0', '0', '1'],
        ['1', '1', '0', '0', '0'],
        ['0', '0', '1', '0', '0'],
        ['0', '0', '0', '1', '1']
    ]
    s = Solution()
    print(s.numIslands(grid))